#include "problems/300.h"
#include "gtest/gtest.h"
#include <random>

using namespace std;

TEST(TestProblemSolutions, TestProblem300)
{
    problem_300::Solution s;
    vector<int> nums{10, 9, 2, 5, 3, 7, 101, 18};
    ASSERT_EQ(s.lengthOfLIS(nums), s.lengthOfLISUnoptimized(nums));
    nums = {4, 10, 4, 3, 8, 9};
    ASSERT_EQ(s.lengthOfLIS(nums), s.lengthOfLISUnoptimized(nums));
    nums = {4, 4, 3, 3, 3, 3, 3, 3, 3, 8, 8, 8, 9, 8, 9};
    ASSERT_EQ(s.lengthOfLIS(nums), s.lengthOfLISUnoptimized(nums));
}

TEST(TestProblemSolutions, TestProblem300Random_1)
{
    problem_300::Solution s;
    vector<int> nums(1001, 0);
    iota(nums.begin(), nums.end(), -500);
    std::random_device rd;
    std::mt19937 g(rd());
    shuffle(nums.begin(), nums.end(), g);
    ASSERT_EQ(s.lengthOfLIS(nums), s.lengthOfLISUnoptimized(nums));
}

TEST(TestProblemSolutions, TestProblem300Random_2)
{
    problem_300::Solution s;
    vector<int> nums(20, 0);
    iota(nums.begin(), nums.end(), 0);
    std::random_device rd;
    std::mt19937 g(rd());
    for (int i = 0; i < 10; ++i)
    {
        shuffle(nums.begin(), nums.end(), g);
        ASSERT_EQ(s.lengthOfLIS(nums), s.lengthOfLISUnoptimized(nums));
    }
}